\documentclass[11pt]{article}
\usepackage[latin1]{inputenc} 
\usepackage[french,english]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{tikz}

\def\P{\mathcal{P}}
\def\prf{\textbf{Proof.}~}
\newtheorem{proposition}{Proposition}

\begin{document}

\section{Definitions}

\subsection{Trees}

A tree is an ordered set $(T,\leq)$ such that :
\begin{itemize}
\item Every couple admits lower bounds (called ancestors) and the set of lower bounds of a couple is totally ordered.
$$\forall \alpha,\beta \in T, \exists \gamma \in T (\gamma \leq \alpha \wedge \gamma \leq \beta) \wedge ((\exists \delta \in T \delta \leq \alpha,\delta \leq \beta) \Rightarrow (\delta \leq \gamma \vee \gamma \leq \delta))$$
\item No non-ordered couple admits an upper bound.
$$\forall \alpha,\beta \in T (\exists \delta \in T \delta \geq \alpha \wedge \delta \geq \beta) \Rightarrow (\alpha \leq \beta \vee \beta \leq \alpha)$$
\end{itemize}

We call leaves the items such that no other item is lower to them and internal vertices all the other items.

Let $a,b$ two vertices and $\alpha$ an ancestor of them. We say that two vertices belong to the same subtree according to $\alpha$ and write $a\sim_{\alpha}b$ if they have an ancestor bigger than $\alpha$:
$$a\sim_{\alpha}b \Leftrightarrow \exists \beta > \alpha, a \geq \beta \wedge b \geq \beta $$

Notice that this relation is transitive. If $a\sim_{\alpha} b$ and $b \sim_{\alpha} c$ then $a,b > \beta_1, b,c > \beta_2$, in particular $b > \beta_1,\beta_2$. This implies that $\beta_1$ and $\beta_2$ are ordered, so the smallest one is smaller than $a,b,c$ and finally $a\sim_{\alpha} c$.

We also write $a\sim_{\alpha}b$ if $a \ngeq \alpha$ and $b \ngeq \alpha$. One can see now that $\sim_{\alpha}$ is a relation of equivalence on the vertices. We write $T/\sim_{\alpha}$ the set of its classes of equivalence.\\

\subsection{Partition Trees}

Let $E$ a set. A partition $\alpha = (A_i)_{i\in I}$ on $E$ is a family of subsets $A_i \subset E$ such that $\bigcup_{i\in I} A_i = E$ and $\forall i,j, A_i \cap A_j = \emptyset$. Let $\P$ a set of partitions. For simplicity we note $(\alpha,\beta) = \alpha \cap \beta, (\alpha,A) = (\alpha,\{A\})$. On the contrary, we use the distinct notations $\alpha\setminus B = \{A\cap B^c,A \in \alpha\} \neq \alpha\setminus\{B\} = \{A \in \alpha, A\neq B\}.$\\

A partitioning tree $PT$ on a set $E$ and a set of partitions $\P$ is a tree such that there exists a bijection between $E$ and the leaves of $PT$ and a mapping of the internal vertices of $PT$ on $\P$. Additionnally, for every internal vertex $\alpha \in PT$, the following condition must be true:
\begin{itemize}
\item there exists a unique $A_i \in \alpha$ that contains all the leaves which are non-ordered with $\alpha$, while the other leaves are scattered among $\alpha \setminus \{A_i\}$.
\item Two leaves belong to the same subtree according to $\alpha$ if and only if they belong to the same $A_j$.
\end{itemize}
In other terms, the elements of $\alpha$ are the classes of equivalence of $E$ for $\sim_{\alpha}$ : $\alpha = PT/\sim_{\alpha}$\\

\subsection{Relaxed Partition Trees}

We can also give a relaxed version of this definition. For that we need to introduce the concept of  neighborhood. Let $T$ a tree, $\alpha$ an internal vertex and $x > \alpha$. Let $\tilde{x}_{\alpha}$ the class of equivalence of $x$ according to $\sim_{\alpha}$.

We call neighborhood according to $\tilde{x}_{\alpha}$ the set of subsets:
$$\mathcal{V}(\tilde{x}_{\alpha})=\{\{ \alpha < \beta < \gamma \},\gamma\in \tilde{x}_{\alpha} \}$$
If $x\ngeq \alpha$, the definition is slightly different:
$$\mathcal{V}(\tilde{x}_{\alpha})=\{\{ \alpha > \beta > \gamma \},\gamma < \alpha \}$$

Let $E$ a set, $\P$ a set of partitions on $E$ and $RT$ a tree. We fix a mapping $\nu$ of $RT$ on $\P$, and for each $\alpha \in RT$ a mapping $\mu_{\alpha}$ of $\alpha$ on $RT/\sim_{\alpha}$.

Additionnally, for every couple $\alpha,\beta \in RT$, the following conditions must be true. Let
$$N(\alpha,\beta) = \bigcap_{V \in \mathcal{V} (\tilde{\beta}_{\alpha})} \bigcup_{x \in V}\tilde{\alpha}_{x}$$
Then:
\begin{equation*}
N(\alpha,\beta) \cap \tilde{\beta}_{\alpha} = N(\beta,\alpha) \cap \tilde{\alpha}_{\beta} = \emptyset
\end{equation*}

Notice that a partition tree is a relaxed partition tree such that $N(\alpha,\beta) \cup \tilde{\beta}_{\alpha} = E$ for all $\alpha,\beta$. One of our problems is to determine when it is possible to build a partition tree out of a relaxed one.

\subsection{Pushing set of partitions}

Let $\alpha,\beta$ two families of subsets. We call overlap and we write
$$O(\alpha,\beta) = \bigcup_{A\in\alpha} A \cap bigcup_{B\in\beta} B$$

We say that a set of partitions $\P$ is "pushing" if:
$$ \forall (A,\alpha),(B,\beta) \in \P,$$
$$ (O(\alpha,\beta)\neq \emptyset)\Rightarrow (\exists F\subset O(\alpha,\beta),F\neq \emptyset,((A\cup F,\alpha\setminus F)\in \P) \vee (B\cup F,\beta\setminus F)\in \P))$$
Intuitively, if two partitions still overlap when we remove a given set in each one, it is possible to increase the size of one of these sets without exiting $\P$.

\subsection{Closed set of partitions}

Let $\P$ a set of partitions. We say that $\P$ is "closed" if:
$$ \forall (A,\alpha) \in P, \forall \mathcal{F} \subset 2^E,$$
$$ \forall \Phi \text{ finite subset of } \mathcal{F}, (A\cup \bigcup_{F \in \Phi}{F},\alpha\setminus \bigcup_{F \in \Phi}{F})\in \P) \Rightarrow (A\cup \bigcup_{F \in \mathcal{F}}{F},\alpha\setminus \bigcup_{F \in \mathcal{F}}{F})\in \P)$$

%\subsection{Brambles}
%
%A bramble $Br$ over $\P$ is a set of subsets of $E$ such that :
%\begin{itemize}
%\item $Br$ meets every partition.
%$$\forall \alpha \in \P, \alpha \cap Br \neq \emptyset$$
%\item Items of $Br$ are pairwise intersecting.
%$$\forall A,A' \in Br, A \cap A' \neq \emptyset$$
%\end{itemize}

\section{Pushing is Refining}

\begin{proposition}
Let $T$ a relaxed partition tree on $\P$. If $\P$ is pushing and closed, then it is possible to build a partition tree $T'$ on $\P$.
\end{proposition}

\prf


\end{document}